Búsqueda y ordenamiento: la base para manejar grandes volúmenes de datos

La búsqueda y el ordenamiento no solo son el inicio de un curso de algoritmos, sino también la lógica fundamental de cómo la ciencia de la computación maneja los datos. El valor de los datos depende de la eficiencia con la que se pueden recuperar y organizar. En esta sección, exploramos el concepto más básico debúsqueda secuencialel núcleo de la evaluación de algoritmos: es decir, cómo localizar un objetivo mediante comparaciones lineales bajo diferentes formas de datos.

1. Lógica y costo

Búsqueda secuencial:从列表中的第一个元素开始，沿着默认的顺序逐个查看，直到找到目标元素或者查完列表。其时间复杂度是 $O(n)$.

2. Comparación de rendimiento: desordenado frente a ordenado

Enlistas desordenadasen las listas desordenadas (véase la tabla a continuación), el número promedio de comparaciones suele ser proporcional a $n$, independientemente de si la búsqueda tiene éxito o no. En cambio, enlistas ordenadaslas listas ordenadas, se puede aprovechar la regla de ordenación para lograr una "terminación anticipada": cuando se encuentra un elemento mayor que el valor objetivo, se puede determinar inmediatamente que el objetivo no existe. Aunque esto no cambia la esencia de $O(n)$, mejora la eficiencia promedio en búsquedas fallidas.